import java.util.ArrayList;

public class SpiralOrder {
    // 螺旋矩阵
    // https://www.nowcoder.com/practice/7edf70f2d29c4b599693dc3aaeea1d31?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public ArrayList<Integer> spiralOrder (int[][] matrix) {
        // write code here
        ArrayList<Integer> ret = new ArrayList<>();
        int top = 0;
        int bottom = matrix.length-1;
        if (bottom < 0) {
            return ret;
        }
        int left = 0;
        int right = matrix[0].length-1;
        if (right < 0) {
            return ret;
        }
        while (true) {
            for (int j = left; j <= right; j++) {
                ret.add(matrix[top][j]);
            }
            top++;
            if (top > bottom) {
                break;
            }
            for (int i = top; i <= bottom; i++) {
                ret.add(matrix[i][right]);
            }
            right--;
            if (right < left) {
                break;
            }
            for (int j = right; j >= left; j--) {
                ret.add(matrix[bottom][j]);
            }
            bottom--;
            if (bottom < top) {
                break;
            }
            for (int i = bottom; i >= top; i--) {
                ret.add(matrix[i][left]);
            }
            left++;
            if (left > right) {
                break;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        SpiralOrder s = new SpiralOrder();
        int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        System.out.println(s.spiralOrder(matrix));
    }
}
